package 热题100;

import java.util.PriorityQueue;

public class 热题23合并k个升序链表 {

    public ListNode mergeKLists1(ListNode[] lists) {
        if (lists == null || lists.length == 0){
            return null;
        }
        if (lists.length == 1){
            return lists[0];
        }

        ListNode dummyHead = new ListNode();
        ListNode cur = dummyHead;
        PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>( (o1,o2) -> Integer.compare(o1.val,o2.val));//默认是最小堆
        for (ListNode node : lists){
            if (node != null){
                queue.add(node);
            }
        }

        while (!queue.isEmpty()){
            cur.next = queue.poll();
            cur = cur.next;
            if (cur.next != null) {
                queue.add(cur.next );
            }
        }

        return dummyHead.next;
    }





    //两两之间合并
    public ListNode mergeKLists(ListNode[] lists) {

        if (lists == null || lists.length == 0){
            return null;
        }

        if (lists.length == 1){
            return lists[0];
        }

        ListNode dummyHead = lists[0];

        for (int i = 1; i < lists.length; i++) {
            dummyHead = combTwoList(dummyHead,lists[i]);
        }
        return dummyHead;
    }
    //合并连个链表
    public ListNode combTwoList(ListNode root1,ListNode root2){
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while (root1 != null && root2 != null){
            if (root1.val < root2.val){
                cur.next = root1;
                root1 = root1.next;
            }else {
                cur.next = root2;
                root2 = root2.next;
            }
            cur = cur.next;
        }
        cur.next = root1 == null ? root2 : root1;
        return dummy.next;
    }
}
